/*
提交链接：https://leetcode.cn/problems/magnetic-force-between-two-balls/submissions/568582653/
1552. 两球之间的磁力-中等
完成日期：2024/9/15
二分搜索
*/

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    // 主函数，返回最大距离
    int maxDistance(vector<int>& position, int m) {
        // 辅助函数，计算在给定间距 x 下可以放下的球的数量
        auto count = [&](int x) -> int {
            int pre = position[0]; // 初始化第一个球的位置
            int cnt = 1; // 统计可以放下球的个数
            for (int i = 1; i < position.size(); ++i) { // 遍历后续位置
                if (position[i] - pre >= x) { // 判断当前位置与上一个球的位置是否满足间距要求
                    pre = position[i]; // 更新上一个球的位置
                    cnt++; // 增加可放下的球的数量
                }
            }
            return cnt; // 返回可以放下的球的数量
        };

        sort(position.begin(), position.end()); // 排序以方便进行二分查找
        int left = 1, right = position.back() - position.front(), ans = -1; // 初始化左右边界

        while (left <= right) { // 闭区间二分查找
            int mid = (left + right) / 2; // 计算中点
            if (count(mid) >= m) { // 如果可以放下 m 个球，增大间距 x
                left = mid + 1;
            } else { // 如果不能放下 m 个球，减小间距 x
                right = mid - 1;
            }
        }

        return right; // 返回最大可行的间距
    }
};